class Solution {
public:
    int totalNQueens(int n) {
        int colMask = 0, diagMask = 0, rDiagMask = 0;
        auto dfs = [&](auto&& dfs, int level){
            int ret = 0;
            if(level == n){
                return 1;
            }
            for(int i = 0; i < n; ++i){     //i是列标号
                int d = n - 1 + level - i;  //对角线编号
                int rd = level + i;         //逆对角线编号

                if( !(colMask >> i & 1) &&  //当前列未放置棋子
                    !(diagMask >> d & 1) && //当前对角线未放置棋子
                    !(rDiagMask >> rd & 1)){//当前逆对角线未放置棋子
                    //置位
                    colMask |= 1 << i;
                    diagMask |= 1 << d;
                    rDiagMask |= 1 << rd;
                    //继续找下一层
                    ret += dfs(dfs, level + 1);
                    //取消置位
                    colMask ^= 1 << i;
                    diagMask ^= 1 << d;
                    rDiagMask ^= 1 << rd;
                }
            }
            return ret;
        };
        return dfs(dfs, 0);
    }
};